package Stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

  public static void main(String[] args) {
//    后缀表达式
//    String suffixExpression = "30 4 + 5 * 6 -";// (30+4)*5-6=164
//    List<String> rpnList = getListString(suffixExpression);
//    System.out.println(rpnList);
//
//    System.out.println("计算结果为：" + calculate(rpnList));


//    测试中缀表达式转后缀
//    ArrayList [1,+,((,2+,3,),*,4,),-,5] =》ArrayList [1,2,3,+,4,*,+,5,-]

    String infixExpression = "1+((2+3)*4)-5";
    List<String> stringList = toInfixExpressionList(infixExpression);
    System.out.println(stringList);

//    后缀表达式
    List<String> toSuffixExpressionList = toSuffixExpressionList(stringList);
    System.out.println("后缀表达式：" + toSuffixExpressionList);

    System.out.println(calculate(toSuffixExpressionList));
  }

//   将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
  public static List<String> getListString(String suffixExpression){
    List<String> list = new ArrayList<>();
    String[] split = suffixExpression.split(" ");
    for (String ele : split) {
      list.add(ele);
    }
    return list;
  }
//  完成计算
  public static int calculate(List<String> list){
    Stack<String> stack = new Stack<>();
    for (String ele : list) {
      if (ele.matches("\\d+")){//如果是数字，则入栈
        stack.push(ele);
      }else {
        int num2 = Integer.parseInt(stack.pop());
        int num1 = Integer.parseInt(stack.pop());
        int res = 0;
        if (ele.equals("+")){
          res = num1 + num2;
        }else if (ele.equals("-")){
          res = num1 - num2;
        }else if (ele.equals("*")){
          res = num1 * num2;
        }else if (ele.equals("/")){
          res = num1/num2;
        }else {
          throw new RuntimeException("运算符有误");
        }
        stack.push(String.valueOf(res));
      }
    }
    return Integer.parseInt(stack.pop());
  }

//  将中缀表达式转成对应的list
  public static List<String> toInfixExpressionList(String s){

    List<String> list = new ArrayList<String>();
    char c ;
    String str;
    int i = 0;
    do {
//      非数字
      if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57){
        list.add("" + c);
        i++;
      }else {
        str = "";
        while (i<s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57){
          str = str + c;
          i++;
        }
        list.add("" + str);
      }
    }while (i < s.length());
    return list;
  }
/*
初始化两个栈:运算符栈s1和储存中间结果的栈s2;
从左至右扫描中缀表达式;
遇到操作数时，将其压s2;
遇到运算符时，比较其与s1栈顶运算符的优先级:
如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈;否则，若优先级比栈顶运算符的高，也将运算符压入s1;
否则，将s1栈顶的运算符弹出并压入到s2中

 */
  public static List<String> toSuffixExpressionList(List<String> s){
    //说明:因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
    //因此比较麻烦,这里我们就不用Stack<String>直接使用List<String> s2
    Stack<String> s1 = new Stack<>();
//    Stack<String> s2 = new Stack<>();
    List<String> s2 = new ArrayList<>();
    for (String ele : s) {
      if (ele.matches("\\d+")){
        s2.add(ele);
      }else if (ele.equals("(")){
        s1.push(ele);
      }else if (ele.equals(")")){
//        如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
        while(!s1.peek().equals("(")){
          s2.add(s1.pop());
        }
//        将“（”弹出
        s1.pop();
      }else{
//        当ele的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中,
        while (s1.size()!=0 && Operation.getValue(s1.peek()) >= Operation.getValue(ele)){
          s2.add(s1.pop());
        }
//        还需要将符号加入到s1
        s1.push(ele);
      }
    }
//    将s1中剩余的运算符依次弹出并加入s2
    while (s1.size()!=0){
      s2.add(s1.pop());
    }

    return s2;
  }
}

//运算符优先级的类
class Operation{
  private static int ADD = 1;
  private static int SUB = 1;
  private static int DIV = 2;
  private static int MUL = 2;

  public static int getValue(String operation){
    int res = 0;
    switch (operation) {
      case "+":
        res = 1;
        break;
      case "-":
        res = 1;
        break;
      case "*":
        res = 2;
        break;
      case "/":
        res = 2;
        break;
      default:
        System.out.println("没有该运算符");
        break;
    }
    return res;
  }
}
